import java.util.Random;

public class test1 {
    //力扣  最小k个数
    public int[] smallestK(int[] arr, int k) {
        qsort(arr, k, 0, arr.length - 1);
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = arr[i];
        }
        return ret;
    }

    public void qsort(int[] nums, int k, int l, int r) {
        if (l >= r) {
            return;
        }
        int key = nums[new Random().nextInt(r - l + 1) + l];

        int left = l - 1, right = r + 1, i = l;
        while (i < right) {
            if (nums[i] < key) swap(nums, ++left, i++);
            else if (nums[i] == key) i++;
            else swap(nums, --right, i);
        }
        int c = r - right + 1;
        int b = right - 1 - left - 1 + 1;
        int a = left - l + 1;
        //小于的数量大于k，说明应该在小于的部分找
        if (a >= k) qsort(nums, k, l, left);
            //等于的部分加小于的部分>=k，说明答案的部分已全在左边和中间部分，直接返回
        else if (b + a >= k) return;
            //执行到这里说明答案有一部分在右边应该到右边找最小k-a-b个数
        else qsort(nums, k - b - a, right, r);
    }

    public void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
